package com.leetcodehot.problems;

import java.util.Arrays;

public class problems70 {
    /**
     * 递归，memo
     */
    /*private int n;
    private int[] memo;

    public int climbStairs(int n) {
        this.n = n;
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return dfs(n);
    }

    private int dfs(int n) {
        if (n < 2) return 1;
        if (memo[n] != -1) return memo[n];
        int res = dfs(n - 1) + dfs(n - 2);
        memo[n] = res;
        return res;
    }*/

    /**
     * 归
     */
    /*public int climbStairs(int n) {
        int[] f = new int[n + 2];
        f[0] = f[1] = 1;
        for (int i = 0; i < n - 1; i++) {
            f[i + 2] = f[i + 1] + f[i];
        }
        return f[n];
    }*/

    /**
     * 空间优化
     */
    public int climbStairs(int n) {
        int f0 = 1;
        int f1 = 1;
        for (int i = 0; i < n - 1; i++) {
            int newF = f1 + f0;
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }
}
